package cn.algorithm;

/**
 * 最大公约数
 *
 * @author dunlingiz
 * @date 2024/3/25
 */
public class MaxCommonDivisor {

    /**
     * 辗转相除法
     * 原理：设有两个正整数a和b，其中a大于b，它们的最大公约数可以通过以下步骤求得：
     * 将a除以b，得到余数r（0 ≤ r < b）。
     * 如果r为0，则b即为两数的最大公约数。
     * 如果r不为0，则将b作为新的a，r作为新的b，重复上述过程。
     */
    public static int calc(int a, int b) {
        int max = Math.max(a, b);
        int min = Math.min(a, b);
        int remainder = max % min;

        if (remainder == 0) {
            return min;
        }
        return calc(min, remainder);
    }
}
